হিপ (Heap) একটি বিশেষ ধরনের ডেটা স্ট্রাকচার যা পূর্ণ বাইনারি ট্রি ভিত্তিক। এটি প্রধানত দুটি ধরনের হয়: ম্যাক্স হিপ (Max Heap) এবং মিন হিপ (Min Heap)। ম্যাক্স হিপে, প্রতিটি পিতার মান তার সন্তানের মানের চেয়ে বড় হয়, এবং মিন হিপে, প্রতিটি পিতার মান তার সন্তানের মানের চেয়ে ছোট হয়। হিপটি মূলত একটি সিকোয়েন্স বা প্যারেন্ট-চাইল্ড সম্পর্কযুক্ত ডেটার সংরক্ষণ ও পরিচালনার জন্য ব্যবহৃত হয়।
হিপ অপারেশনসমূহ
১. ইনসার্ট (Insert)
বিবরণ: একটি নতুন উপাদান হিপে যুক্ত করার প্রক্রিয়া।
কাজের পদ্ধতি:
- নতুন উপাদানটি হিপের শেষের দিকে যোগ করা হয় (এটি একটি পূর্ণ বাইনারি ট্রির নিয়ম অনুসরণ করে)।
- নতুন উপাদানটির জন্য পিতার সাথে তুলনা করা হয় এবং প্রয়োজনে এটি উপরে উঠানো হয় (বাবা উপরে যেতে থাকে)।
- এই প্রক্রিয়াটি চলতে থাকে যতক্ষণ না হিপের গঠন বজায় থাকে।
উদাহরণ (ম্যাক্স হিপ):
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[i] < arr[left]:
largest = left
if right < n and arr[largest] < arr[right]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # বিনিময়
heapify(arr, n, largest)
def insert(arr, key):
arr.append(key) # নতুন উপাদান যুক্ত করা
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i) # হিপ গঠন বজায় রাখা
# ব্যবহার
heap = [10, 20, 30]
insert(heap, 25)
print(heap) # আউটপুট: [30, 20, 10, 25]
২. ডিলিট (Delete)
বিবরণ: হিপ থেকে সর্বাধিক (ম্যাক্স হিপ) বা সর্বনিম্ন (মিন হিপ) উপাদান মুছে ফেলার প্রক্রিয়া।
কাজের পদ্ধতি:
- রুট উপাদান (ম্যাক্স বা মিন) মুছে ফেলুন।
- হিপের শেষ উপাদানকে রুটের স্থানে রাখুন।
- নতুন রুটের জন্য হিপ গঠন বজায় রাখুন।
উদাহরণ (ম্যাক্স হিপ):
def delete_root(arr):
n = len(arr)
if n == 0:
return None
if n == 1:
return arr.pop() # একমাত্র উপাদান মুছে ফেলুন
root = arr[0] # রুট সংরক্ষণ করুন
arr[0] = arr[-1] # শেষ উপাদানকে রুটে রাখুন
arr.pop() # শেষ উপাদান মুছে ফেলুন
heapify(arr, n - 1, 0) # হিপ গঠন বজায় রাখা
return root # রুটের মান রিটার্ন করুন
# ব্যবহার
heap = [30, 20, 10]
print(delete_root(heap)) # আউটপুট: 30
print(heap) # আউটপুট: [20, 10]
৩. এক্সট্র্যাক্ট-ম্যাক্স/মিন (Extract-Max/Min)
বিবরণ: সর্বাধিক (ম্যাক্স হিপের জন্য) বা সর্বনিম্ন (মিন হিপের জন্য) উপাদানটি বের করার প্রক্রিয়া।
কাজের পদ্ধতি:
- রুট উপাদানটি (সর্বাধিক বা সর্বনিম্ন) ফিরিয়ে দিন।
- ডিলিট অপারেশনটি ব্যবহার করে রুট উপাদানটিকে হিপ থেকে সরান।
উদাহরণ (ম্যাক্স হিপ):
def extract_max(arr):
if len(arr) == 0:
return None
return delete_root(arr) # সর্বাধিক উপাদান বের করুন
# ব্যবহার
heap = [30, 20, 10]
print(extract_max(heap)) # আউটপুট: 30
print(heap) # আউটপুট: [20, 10]
উপসংহার
হিপ অপারেশনগুলি যেমন ইনসার্ট, ডিলিট, এবং এক্সট্র্যাক্ট-ম্যাক্স/মিন গুরুত্বপূর্ণ ডেটা পরিচালনার কৌশল। এগুলি বিভিন্ন প্রোগ্রামিং সমস্যায়, যেমন সর্বাধিক বা সর্বনিম্ন মান বের করতে, অথবা অর্ডারড ডেটা গঠন করতে ব্যবহৃত হয়। হিপের কার্যকারিতা ও সময় জটিলতা O(log n) হওয়ার কারণে, এটি দ্রুত কাজ করার জন্য উপযুক্ত।
Read more
